package com.mj.tree;

import java.util.Comparator;

/**
 * E extends Comparable
 * E 这个类必须遵守Comparable 实现接口
 * <p>
 * 二叉搜索树必须拥有可比较的特点
 *
 * @param <E>
 */
public class BST<E> extends BinaryTree<E> {
    private Comparator<E> comparator;

    public BST() {
        this(null);
    }

    public BST(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    /**
     * @param element1
     * @param element2
     * @return 返回值等于0，代表e1和e2相等；返回值大于0，代表e1大于e2；返回值小于于0，代表e1小于e2
     */
    private int compare(E element1, E element2) {
        if (comparator != null)
            return comparator.compare(element1, element2);
        //强制转换为Comparable接口的实现类
        return ((Comparable<E>) element1).compareTo(element2);

    }

    // 添加元素
    public void add(E element) {
        elementNotNullCheck(element);
        //第一种情况 根节点为空时
        if (root == null) {
            //根节点没有头节点
            root = new Node<>(element, null);
            size++;
            return;
        }
        //往根节点添加元素
        Node<E> node = root;
        Node<E> parent = root;
        int compare = 0;
        while (node != null) {
            compare = compare(element, node.element);
            //在移动之前 先把父节点保存起来
            parent = node;
            if (compare > 0) {
                node = node.right;
            } else if (compare < 0) {
                node = node.left;
            } else {
                //覆盖
                node.element = element;
                return;
            }
        }
        Node<E> newNode = new Node<>(element, parent);
        if (compare > 0) parent.right = newNode;
        else parent.left = newNode;

        size++;
    }


    // 删除元素**
    public void remove(E element) {
        remove(node(element));
    }

    private void remove(Node<E> node) {
        if (node == null) return;

        //特殊处理度为2的节点，做到删除度为1或度为0的节点时代码复用
        if (node.hasTwoChildren()) { //度为2的节点
            //找到后继节点
//            Node<E> predecessor = predecessor(node);
            Node<E> s = successor(node);
            //用后继节点的值覆盖度为2的节点的值
            node.element = s.element;
            //将node指向后继节点，然后删除node节点（successor）
            node = s;
        }
        //删除node节点（node的度必然是 1或0）
        Node<E> replacement = node.left != null ? node.left : node.right;
        //node的度必然是 1
        if (!node.isLeaf()) replacement.parent = node.parent;          //修改父节点

        //更改parent的left. right的指向
        if (node.parent == null) root = replacement;//node是度为1的节点并且是根节点
        else if (node == node.parent.right) node.parent.right = replacement;
        else if (node == node.parent.left) node.parent.left = replacement;
        size--;
    }

    /**
     * 通过元素获取节点
     *
     * @param element
     * @return
     */
    private Node<E> node(E element) {
        Node<E> node = this.root;
        while (node != null) {
            int com = compare(element, node.element);
            if (com == 0) return node;
            if (com > 0) node = node.right;
            else node = node.left;// com < 0
        }
        return null;
    }

    // 是否包含某元素
    public boolean contains(E element) {
        return node(element) != null;
    }

    /**
     * 检查元素是否为空
     */
    private void elementNotNullCheck(E element) {
        if (element == null)
            throw new IllegalArgumentException("element must not be null");
    }

}
